# O(n^2)
# class Solution(object):
#     def findNumberOfLIS(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         n = len(nums)
#         t_max_len = 0
#         max_count = 0
#         DP = [[1, 1] for _ in range(n)]
#         for i in range(n):
#             for j in range(i):
#                 if nums[j] < nums[i]:
#                     if DP[j][0] + 1 > DP[i][0]:
#                         DP[i][0] = DP[j][0] + 1
#                         DP[i][1] = DP[j][1]
#                     else:
#                         if DP[j][0] + 1 == DP[i][0]:
#                             DP[i][1] += DP[j][1]
#             if DP[i][0] > t_max_len:
#                 max_count = DP[i][1]
#                 t_max_len = DP[i][0]
#             else:
#                 if DP[i][0] == t_max_len:
#                     max_count += DP[i][1]
#
#         return max_count
# O(nlogn)
class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        st = [[[nums[0], 1]]]

        def find1(val):
            left = 0
            right = len(st) - 1
            while left < right:
                mid = (left + right + 1) // 2
                if val <= st[mid][-1][0]:
                    right = mid - 1
                else:
                    left = mid
            if st[left][-1][0] >= val:
                return left - 1
            else:
                return left

        def find2(k, val):
            left = 0
            right = len(st[k]) - 1
            while left < right:
                mid = (left + right) // 2
                if st[k][mid][0] >= val:
                    left = mid + 1
                else:
                    right = mid
            return left

        n = len(nums)
        for i in range(1, n):
            if nums[i] > st[-1][-1][0]:
                left = find2(-1, nums[i])
                if left == 0:
                    st.append([[nums[i], st[-1][-1][1]]])
                else:
                    st.append([[nums[i], st[-1][-1][1] - st[-1][left - 1][1]]])
            else:
                k = find1(nums[i])
                if k < 0:
                    if nums[i] == st[0][-1][0]:
                        st[0][-1][1] += 1
                    else:
                        st[0].append([nums[i], 1 + st[0][-1][1]])
                else:
                    left = find2(k, nums[i])
                    if left == 0:
                        add_num = st[k][-1][1]
                    else:
                        add_num = st[k][-1][1] - st[k][left - 1][1]
                    if nums[i] == st[k + 1][-1][0]:
                        st[k + 1][-1][1] += add_num
                    else:
                        st[k + 1].append([nums[i], add_num + st[k + 1][-1][1]])
        print(st)
        return st[-1][-1][1]


data = Solution()
# nums = [1, 3, 5, 4, 7]
# print(data.findNumberOfLIS(nums))
nums = [10, 2, 5, 3, 7, 101, 4, 6, 5]
print(data.findNumberOfLIS(nums))
